#include<iostream>
#include<vector>
using namespace std;
class Solution {
void roll(int &ans,int &i,int &j,int &k)
{
    i=j;
    j=k;
    k=ans;
}
public:
    int tribonacci(int n) {
        //vector<int>dp(40,0);
        //dp[0]=0,dp[1]=1,dp[2]=1;

        ////o(n)时间复杂度 o(n)时间复杂度
        //for(int i=3;i<=n;i++)
        //{
            //dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        //}

        /*
        滚动数组优化
        */
        if(n==0)return 0;
        if(n==1||n==2)return 1;
        int i=0,j=1,k=1;
        int ans=0;
        for(int m=3;m<=n;m++)
        {
            ans=i+j+k;
            roll(ans,i,j,k);   
        }

        return ans;
    }
};